#ifndef GRAPHSTRUCTURES_H
#define GRAPHSTRUCTURES_H

#if _MSC_VER > 1000
#pragma once
#endif

#include "AutoTypeStructs.h"

#if defined(LINUX)
#include <float.h>
#endif

struct GraphNode;

class CSmartObjectClass;
class CSmartObject;
struct SmartObjectHelper;
class CGraphNodeManager;

enum EObstacleFlags
{
	OBSTACLE_COLLIDABLE =	BIT(0),
	OBSTACLE_HIDEABLE =		BIT(1),
};

enum
{
	eLT_DirectLink = 0,
	eLT_ReversedLink,
	eLT_TotalLinkTypes
};

struct ObstacleData
{
	Vec3 vPos;
	Vec3 vDir;
	/// this radius is approximate - it is estimated during link generation. if -ve it means
	/// that it shouldn't be used (i.e. object is significantly non-circular)
	float fApproxRadius;
	uint8 flags;
	uint8 approxHeight;	// height in 4.4 fixed point format.

	inline void SetCollidable(bool state) { state ? (flags |= OBSTACLE_COLLIDABLE) : (flags &= ~OBSTACLE_COLLIDABLE); }
	inline void SetHideable(bool state) { state ? (flags |= OBSTACLE_HIDEABLE) : (flags &= ~OBSTACLE_HIDEABLE); }
	inline bool IsCollidable() const { return (flags & OBSTACLE_COLLIDABLE) != 0; }
	inline bool IsHideable() const { return (flags & OBSTACLE_HIDEABLE) != 0; }

	/// Sets the approximate height and does the necessary conversion. 
	inline void SetApproxHeight(float h) { approxHeight = (uint8)(clamp(h * (1 << 4), 0.f, 255.f)); }
	/// Returns the approximate height and does the necessary conversion. 
	inline float GetApproxHeight() const { return (float)approxHeight / (float)(1 << 4); }
	/// Gets the navigation node that this obstacle is attached to (and caches the result). The result should be
	/// safe in game, but might be invalid in editor if the navigation gets modified whilst AI/physics is running
	/// so I advise against dereferencing the result (unless you validate it first).
	/// The calculation assumes that this obstacle is only attached to triangular nodes
	const std::vector<const GraphNode*>& GetNavNodes() const;
	void ClearNavNodes() { navNodes.clear(); needToEvaluateNavNodes = true; }
	// mechanisms for setting the nav nodes on a temporary obstacle object
	void SetNavNodes(const std::vector<const GraphNode*>& nodes);
	void AddNavNode(const GraphNode* pNode);

	/// Note - this is used during triangulation where we can't have two objects
	/// sitting on top of each other - even if they have different directions etc
	bool operator==(const ObstacleData& other) const { return ( (fabs(vPos.x - other.vPos.x) < 0.001f) && (fabs(vPos.y - other.vPos.y) < 0.001f) ); }

	ObstacleData(const Vec3& pos = Vec3Constants<float>::fVec3_Zero, const Vec3& dir = Vec3Constants<float>::fVec3_Zero) :
		vPos(pos), vDir(dir), fApproxRadius(-1.f), approxHeight(0), flags(OBSTACLE_COLLIDABLE), needToEvaluateNavNodes(true) {}

	void Serialize(TSerialize ser);

private:
	// pointer to the triangular navigation nodes that contains us (result of GetEnclosing). 
	mutable std::vector<const GraphNode *> navNodes;
	mutable bool needToEvaluateNavNodes;
};

// DynArray take only one pointer in memory
#ifdef _DEBUG
typedef std::vector<ObstacleData>	Obstacles;
typedef std::vector<int>			ObstacleIndexVector;
#else
#include <CryArray.h>
typedef DynArray<ObstacleData>	Obstacles;
typedef DynArray<int>			ObstacleIndexVector;
#endif

//====================================================================
// GraphLinkBidirectionalData
//====================================================================

struct GraphLinkBidirectionalData
{
	friend class CGraphLinkManager;

	GraphLinkBidirectionalData()
		: fExposure(0.f), vEdgeCenter(ZERO)
	{
		directionalData[eLT_DirectLink].nextLinkIndex = directionalData[eLT_ReversedLink].nextLinkIndex = 0;
		directionalData[eLT_DirectLink].nextNodeIndex = directionalData[eLT_ReversedLink].nextNodeIndex = 0;
		directionalData[eLT_DirectLink].waterDepthInCmHigh = directionalData[eLT_ReversedLink].waterDepthInCmHigh = 0;
		directionalData[eLT_DirectLink].waterDepthInCmLow = directionalData[eLT_ReversedLink].waterDepthInCmLow = 0;
		directionalData[eLT_DirectLink].maxRadiusInCm = directionalData[eLT_ReversedLink].maxRadiusInCm = 0;
		directionalData[eLT_DirectLink].origMaxRadiusInCm = directionalData[eLT_ReversedLink].origMaxRadiusInCm = 0;
		directionalData[eLT_DirectLink].startIndex = directionalData[eLT_ReversedLink].startIndex = 0;
		directionalData[eLT_DirectLink].endIndex = directionalData[eLT_ReversedLink].endIndex = 0;
		directionalData[eLT_DirectLink].simplePassabilityCheck = directionalData[eLT_ReversedLink].simplePassabilityCheck = 0;
	}

private:
	struct DirectionalData
	{
		// maximum size sphere that can pass trough this edge
		signed maxRadiusInCm : 16;

		// links may get modified at run-time - store a copy of their original pass radius
		signed	origMaxRadiusInCm : 16;

		// Links are stored in a linked-list - this is the index of the next link for the nodes at each end.
		unsigned nextLinkIndex : 23;

		// Indicates if a human waypoint link can use simplified walkability check.  For other link
		// types is not applicable.
		//
		// NOTE Apr 26, 2007: <pvl> in order not to undo memory optimization done earlier this
		// member is used in a very tricky way.  In directionalData[eDirectLink] it says whether this
		// link is "simple" while in directionalData[eReversedLink] it indicates if the link "simplicity"
		// has already been computed at all (so when it's 'false' then
		// directionalData[eDirectLink].simplePassabilityCheck cannot be considered valid).
		// This ugliness is encapsulated in GraphLinkManager but anyway ...
		//
		// By doing all of this, I sold my soul to MichaelS.
		unsigned simplePassabilityCheck : 1;

	  // Minimum/maximum (depending on which direction we are talking) water depth over this link in cm.
		// Has to be split up into two to make the bitfields add up to 32 bit blocks (it doesnt seem to pack properly
		// otherwise).
		unsigned waterDepthInCmLow : 8;
		signed waterDepthInCmHigh : 8;

		// next graph node this way	
		unsigned nextNodeIndex : 20;

		// indices of the edge vertices of this edge - only valid for 2D navigation
		// types (triangle and waypoint).
		unsigned startIndex : 2;
		unsigned endIndex : 2;
	};

	DirectionalData directionalData[eLT_TotalLinkTypes];

	/// The exposure associated with this link
	float fExposure;
	Vec3 vEdgeCenter;
};

#include "GraphLinkManager.h"

struct SCachedPassabilityResult
{
  SCachedPassabilityResult() : AABBTestHash(0), OBBTestHash(0), walkableResult(1), aiCollisionEntitiesIndex(1), checkStart(1) {}
  void Reset(unsigned hashValue, bool walkable) {AABBTestHash = hashValue; OBBTestHash = hashValue; walkableResult = walkable; aiCollisionEntitiesIndex = 1; checkStart = 1;}
  unsigned int AABBTestHash;
  unsigned int OBBTestHash;
  // 0 = static, 1 = all, 2 = dynamic etc
  unsigned char aiCollisionEntitiesIndex : 6;
  unsigned char checkStart : 1;
  unsigned char walkableResult : 1;
};
typedef std::vector<unsigned>	VectorOfLinkIds;
struct IVisArea;

class CVertexList;

// NOTE Apr 8, 2008: <pvl> member functions now take a VertexList* argument.
// It's ugly but global access to the vertex list instance is no longer provided.
// It might be possible to factor vertex list dependent functionality out of
// STriangularNavData and get rid of the VertexList* argument but I'm not sure.
struct STriangularNavData
{
  STriangularNavData() : isForbidden(0), isForbiddenDesigner(0) {}
  ObstacleIndexVector vertices;
  /// isForbidden is set for navigation nodes that lie inside a forbidden area
  uint8 isForbidden : 1;
  /// isForbiddenDesigner is only set for nav nodes inside designer forbidden areas
  uint8 isForbiddenDesigner : 1;

  real GetDegeneracyValue(const CVertexList* pVList);
  void MakeAntiClockwise(const CVertexList* pVList);
  bool IsAntiClockwise(const CVertexList* pVList);
  real GetCross(const CVertexList* pVList, CGraphLinkManager& linkManager, const Vec3r& vCutStart, const Vec3r& vDir, unsigned theLink);
};

struct SWaypointNavData
{
  IVisArea *pArea;

  static EWaypointLinkType GetLinkTypeFromRadius(float radius)
  {
    if (abs(radius - WLT_AUTO_PASS) < 0.001f)
      return WLT_AUTO_PASS;
    else if (abs(radius - WLT_EDITOR_PASS) < 0.001f)
      return WLT_EDITOR_PASS;
    else if (abs(radius - WLT_EDITOR_IMPASS) < 0.001f)
      return WLT_EDITOR_IMPASS;
    else if (abs(radius - WLT_AUTO_IMPASS) < 0.001f)
      return WLT_AUTO_IMPASS;
    else
      return WLT_UNKNOWN_TYPE;
  }

  int nBuildingID;
  EWaypointNodeType type;

  // if it's a hide point then store the direction the hide point faces. 
  Vec3 dir;
  // Stores the local up (z) axis of the point - used in nav regions where type = 1 (3D surface)
  Vec3 up;

  SWaypointNavData() : pArea(0), nBuildingID(-1), type(WNT_UNSET), dir(ZERO), up(0, 0, 1) {}
};

struct SFlightNavData
{
  int nSpanIdx;	
//  SFlightNavData() : nSpanIdx(-1) {}
};

struct SVolumeNavData
{
  int	nVolimeIdx;
//  SVolumeNavData() : nVolimeIdx(-1) {}
};

struct SRoadNavData
{
  /// total width of the road at this point
  float fRoadWidth;
  /// offset for driving (+ve is on the right side of the road)

	// As soon as we decided use only Width not needed store this structure separate
  //float fRoadOffset;
  //SRoadNavData() : fRoadWidth(0.0f), fRoadOffset(0.0f) {}
};

struct SSmartObjectNavData
{
  CSmartObjectClass*	pClass;
  SmartObjectHelper*	pHelper;
  CSmartObject*		pSmartObject;
};


//====================================================================
// GraphNode
// In principle this is a constant structure in that the pathfinder
// doesn't modify it. However, in practice during pathfinding it's 
// convenient to cache some info along with the node - hence the
// mutable members
// This structure needs to represent different types of nodes - the basic
// info should just represent the generic navigation info, and the data
// specific to the navigation region lives in navData
//====================================================================
struct GraphNode
{
	/// navType is const so that nodes can be stored in lists of their respective types
	const IAISystem::ENavigationType navType;

	/// The position of the node The position can only be set indirectly so that
	/// the AI system can update any spatial structures containing this node
	const Vec3& GetPos() const { return pos; }

	STriangularNavData* GetTriangularNavData();
	SWaypointNavData* GetWaypointNavData();
	SFlightNavData* GetFlightNavData();
	SVolumeNavData* GetVolumeNavData();
	SRoadNavData* GetRoadNavData();
	SSmartObjectNavData* GetSmartObjectNavData();

	const STriangularNavData* GetTriangularNavData() const;
	const SWaypointNavData* GetWaypointNavData() const;
	const SFlightNavData* GetFlightNavData() const;
	const SVolumeNavData* GetVolumeNavData() const;
	const SRoadNavData* GetRoadNavData() const;
	const SSmartObjectNavData* GetSmartObjectNavData() const;

	/// Used as a flag for costs that aren't calculated yet
	static const float fInvalidCost;


	// Returns the link index that goes to destNode. -1 if no link found
	int GetLinkIndex(CGraphNodeManager& nodeManager, CGraphLinkManager& linkManager, const GraphNode* destNode) const;
	unsigned GetLinkTo(CGraphNodeManager& nodeManager, CGraphLinkManager& linkManager, const GraphNode* destNode) const;
	int GetLinkCount(CGraphLinkManager& linkManager) const;
	void RemoveLinkTo(CGraphLinkManager& linkManager, unsigned nodeIndex);

	/// Returns the maximum radius from all the links
	float GetMaxLinkRadius(CGraphLinkManager& linkManager) const
	{
		float r = -FLT_MAX;
		//for (unsigned i = links.size() ; i-- != 0 ;)
		for (unsigned link = firstLinkIndex; link; link = linkManager.GetNextLink(link))
		{
			r = max(r, linkManager.GetRadius(link));
		}
		return r;
	}

	unsigned FindNewLink(CGraphLinkManager& linkManager);

	bool Release()
	{
		assert(nRefCount>=1);
		--nRefCount;
		return (nRefCount == 0);
	}

	void AddRef()
	{
		assert(nRefCount < std::numeric_limits<TRefCount>::max());
		++nRefCount;
	}

	// this resets our IDs and assigns a unique ID to all the nodes in the container.
	// Should just be called on navigation graph saving. pNodeForID1 is a special node
	// that will have ID 1 assigned to it
	static void ResetIDs(CGraphNodeManager& nodeManager, class CAllNodesContainer& allNodes, GraphNode* pNodeForID1);

	size_t MemStats();

	// This must ONLY be called via the graph node deletion function
	~GraphNode();

protected:
	/// This must ONLY be called via the graph node creation function.
	/// If _ID == 0 then an ID will be assigned automatically 
	GraphNode(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID);

private:
	friend class CGraph;
	friend struct GraphNodesPool;

	void SetPos(const Vec3& newPos) { pos = newPos; }

public:
	// Links are stored in a linked-list - this is the index of the next link for the nodes at each end.
	unsigned firstLinkIndex;

	// Used internally by the pathfinder - there are three attributes normally called
	// f (fitness), g (goal) and h (heuristic) in A*. Since the fitness is just the sum of
	// the other two we calculate it on the fly when needed

	/// Cost from the starting node to this node (g)
	mutable float fCostFromStart;
	/// Estimated cost from this node to the goal (h)
	mutable float fEstimatedCostToGoal;
	/// Previous node in the A* path
	mutable unsigned prevPathNodeIndex; 


private:
	// stuff below here is basically constant (i.e. not modified by pathfinding), unless
	// the world changes.
	// unique ID - preserved when saving. 
	unsigned int ID;

  Vec3	pos;
  /// The pool of free IDs - populated when nodes are deleted
  static std::vector<unsigned int> freeIDs;

  /// The highest ID currently in use (0 is invalid), so maxID+1 is a valid unique ID
  static unsigned int maxID;

public:
	typedef unsigned short TRefCount;
	TRefCount nRefCount;

	/// tag is used internally by the pathfinder - and ONLY by the pathfinder since
	/// it needs to be maintained across pathfinder calls (since the pathfinder can 
	/// be timesliced. The tag is true if this node is on the open or closed lists - 
	/// i.e. the two costs have been calculated/estimated, and are valid for use in
	/// walking back
	mutable unsigned char tag;//:1;

	/// General marker used to help traversing the graph of nodes. If you use this
	/// be careful about calling other functions that use it! Not used by pathfinder
	mutable unsigned char mark;//:1;
};

struct GraphNode_Unset : public GraphNode
{
private:
	friend class CGraph;
	friend struct GraphNodesPool;
	friend class CGraphNodeManager;

	GraphNode_Unset(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID)
		:	GraphNode(type, inpos, _ID) {}

	// This must ONLY be called via the graph node deletion function
	~GraphNode_Unset() {}
};

struct GraphNode_Triangular : public GraphNode
{
private:
	friend struct GraphNode;
	friend class CGraph;
	friend struct GraphNodesPool;
	friend class CGraphNodeManager;

	GraphNode_Triangular(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID)
		:	GraphNode(type, inpos, _ID) {}

	// This must ONLY be called via the graph node deletion function
	~GraphNode_Triangular() {}

	STriangularNavData navData;
};

struct GraphNode_Waypoint : public GraphNode
{
protected:
	friend struct GraphNode;
	friend class CGraph;
	friend struct GraphNodesPool;
	friend class CGraphNodeManager;

	GraphNode_Waypoint(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID)
		:	GraphNode(type, inpos, _ID) {}

	// This must ONLY be called via the graph node deletion function
	~GraphNode_Waypoint() {}

	SWaypointNavData navData;
};

struct GraphNode_WaypointHuman : public GraphNode_Waypoint
{
private:
	friend struct GraphNode;
	friend class CGraph;
	friend struct GraphNodesPool;
	friend class CGraphNodeManager;

	GraphNode_WaypointHuman(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID)
		:	GraphNode_Waypoint(type, inpos, _ID) {}

	// This must ONLY be called via the graph node deletion function
	~GraphNode_WaypointHuman() {}
};

struct GraphNode_Waypoint3DSurface : public GraphNode_Waypoint
{
private:
	friend struct GraphNode;
	friend class CGraph;
	friend struct GraphNodesPool;
	friend class CGraphNodeManager;

	GraphNode_Waypoint3DSurface(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID)
		:	GraphNode_Waypoint(type, inpos, _ID) {}

	// This must ONLY be called via the graph node deletion function
	~GraphNode_Waypoint3DSurface() {}
};

struct GraphNode_Flight : public GraphNode
{
private:
	friend struct GraphNode;
	friend class CGraph;
	friend struct GraphNodesPool;
	friend class CGraphNodeManager;

	GraphNode_Flight(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID)
		:	GraphNode(type, inpos, _ID) {}

	// This must ONLY be called via the graph node deletion function
	~GraphNode_Flight() {}

	SFlightNavData navData;
};

struct GraphNode_Volume : public GraphNode
{
private:
	friend struct GraphNode;
	friend class CGraph;
	friend struct GraphNodesPool;
	friend class CGraphNodeManager;

	GraphNode_Volume(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID)
		:	GraphNode(type, inpos, _ID) {}

	// This must ONLY be called via the graph node deletion function
	~GraphNode_Volume() {}

	SVolumeNavData navData;
};

struct GraphNode_Road : public GraphNode
{
private:
	friend struct GraphNode;
	friend class CGraph;
	friend struct GraphNodesPool;
	friend class CGraphNodeManager;

	GraphNode_Road(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID)
		:	GraphNode(type, inpos, _ID) {}

	// This must ONLY be called via the graph node deletion function
	~GraphNode_Road() {}

	SRoadNavData navData;
};

struct GraphNode_SmartObject : public GraphNode
{
private:
	friend struct GraphNode;
	friend class CGraph;
	friend struct GraphNodesPool;
	friend class CGraphNodeManager;

	GraphNode_SmartObject(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID)
		:	GraphNode(type, inpos, _ID) {}

	// This must ONLY be called via the graph node deletion function
	~GraphNode_SmartObject() {}

	SSmartObjectNavData navData;
};

struct GraphNode_Free2D : public GraphNode
{
private:
	friend struct GraphNode;
	friend class CGraph;
	friend struct GraphNodesPool;
	friend class CGraphNodeManager;

	GraphNode_Free2D(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID)
		:	GraphNode(type, inpos, _ID) {}

	// This must ONLY be called via the graph node deletion function
	~GraphNode_Free2D() {}
};

#include "GraphNodeManager.h"

inline STriangularNavData *GraphNode::GetTriangularNavData() {assert(navType == IAISystem::NAV_TRIANGULAR); return &((GraphNode_Triangular*)this)->navData;}
inline SWaypointNavData *GraphNode::GetWaypointNavData() {assert(navType == IAISystem::NAV_WAYPOINT_3DSURFACE || navType == IAISystem::NAV_WAYPOINT_HUMAN); return &((GraphNode_Waypoint*)this)->navData;}
inline SFlightNavData *GraphNode::GetFlightNavData() {assert(navType == IAISystem::NAV_FLIGHT); return &((GraphNode_Flight*)this)->navData;}
inline SVolumeNavData *GraphNode::GetVolumeNavData() {assert(navType == IAISystem::NAV_VOLUME); return &((GraphNode_Volume*)this)->navData;}
inline SRoadNavData *GraphNode::GetRoadNavData() {assert(navType == IAISystem::NAV_ROAD); return &((GraphNode_Road*)this)->navData;}
inline SSmartObjectNavData *GraphNode::GetSmartObjectNavData() {assert(navType == IAISystem::NAV_SMARTOBJECT); return &((GraphNode_SmartObject*)this)->navData;}

inline const STriangularNavData *GraphNode::GetTriangularNavData() const {assert(navType == IAISystem::NAV_TRIANGULAR); return &((GraphNode_Triangular*)this)->navData;}
inline const SWaypointNavData *GraphNode::GetWaypointNavData() const {assert(navType == IAISystem::NAV_WAYPOINT_3DSURFACE || navType == IAISystem::NAV_WAYPOINT_HUMAN); return &((GraphNode_Waypoint*)this)->navData;}
inline const SFlightNavData *GraphNode::GetFlightNavData() const {assert(navType == IAISystem::NAV_FLIGHT); return &((GraphNode_Flight*)this)->navData;}
inline const SVolumeNavData *GraphNode::GetVolumeNavData() const {assert(navType == IAISystem::NAV_VOLUME); return &((GraphNode_Volume*)this)->navData;}
inline const SRoadNavData *GraphNode::GetRoadNavData() const {assert(navType == IAISystem::NAV_ROAD); return &((GraphNode_Road*)this)->navData;}
inline const SSmartObjectNavData *GraphNode::GetSmartObjectNavData() const {assert(navType == IAISystem::NAV_SMARTOBJECT); return &((GraphNode_SmartObject*)this)->navData;}

inline int GraphNode::GetLinkIndex(CGraphNodeManager& nodeManager, CGraphLinkManager& linkManager, const GraphNode* destNode) const
{
	int i = 0;
	for (unsigned link = firstLinkIndex; link; link = linkManager.GetNextLink(link), ++i)
	{
		if (nodeManager.GetNode(linkManager.GetNextNode(link)) == destNode)
		{
			return i;
		}
	}
	return -1;
}

inline unsigned GraphNode::GetLinkTo(CGraphNodeManager& nodeManager, CGraphLinkManager& linkManager, const GraphNode* destNode) const
{
	for (unsigned link = firstLinkIndex; link; link = linkManager.GetNextLink(link))
	{
		if (nodeManager.GetNode(linkManager.GetNextNode(link)) == destNode)
		{
			return link;
		}
	}
	return 0;
}

inline int GraphNode::GetLinkCount(CGraphLinkManager& linkManager) const
{
	int count = 0;
	for (unsigned link = firstLinkIndex; link; link = linkManager.GetNextLink(link))
	{
		++count;
	}
	return count;
}

inline void GraphNode::RemoveLinkTo(CGraphLinkManager& linkManager, unsigned nodeIndex)
{
	unsigned prevLink = 0;
	for (unsigned link = firstLinkIndex; link;)
	{
		unsigned nextLink = linkManager.GetNextLink(link);
		if (linkManager.GetNextNode(link) == nodeIndex)
		{
			if (!prevLink)
			{
				firstLinkIndex = nextLink;
			}
			else
			{
				linkManager.SetNextLink(prevLink, nextLink);
			}
		}
		prevLink = link;
		link = nextLink;
	}
}

#endif
